# nums=[1,3,2,5,1,2,6,2]
# nums=[2,3,2]
# nums=[1,2,3,1]
# nums=[0]
# nums=[1,1,3,6,7,10,7,1,8,5,9,1,4,4,3]  #41
nums=[8,4,8,5,9,6,5,4,4,10]
def rob(nums):
    numsLenght=len(nums)
    if numsLenght==1:
        return nums[0]
    if numsLenght==2:
        return max(nums[0],nums[1])
    if numsLenght==3:
        return max(nums[0],nums[1],nums[2])
    #创建状态转移矩阵
    dp=[0 for _ in range(numsLenght)]
    state=[False for _ in range(numsLenght)]
    dp[0]=nums[0]
    state[0]=True
    dp[1]=nums[1]
    dp[2]=nums[0]+nums[2]
    state[2]=True
    #循环
    for i in range(3,numsLenght):
        if i==numsLenght-1:
            if state[i-2] and state[i-3]:
                #都是真的,那么就没得选了，该值
                dp[i]=0  #没有可以选择的值
            else:
                if not state[i-2] and not state[i-3]:
                    dp[i]=nums[i]+max(dp[i-2],dp[i-3])
                elif not state[i-2] and state[i-3]:
                    dp[i]=nums[i]+dp[i-2]
                elif not state[i-3] and state[i-2]:
                    dp[i]=nums[i]+dp[i-3]
        else:
            maxValue=max(dp[i-2],dp[i-3])
            dp[i] = maxValue + nums[i]
            if dp[i-2]==dp[i-3]:
                if state[i-2] and state[i-3]:
                    state[i]=True
            else:
                #两个值不一样
                if maxValue==dp[i-2]:
                    state[i]=state[i-2]
                if maxValue==dp[i-3]:
                    state[i]=state[i-3]
    return max(dp)
def m1(nums):
    k1=rob(nums)
    nums.reverse()
    k2=rob(nums)
    print(max(k1,k2))
# m1(nums)


# nums=[1,1,3,6,7,10,7,1,8,5,9,1,4,4,3]  #41
def rob1(nums):
    numsLenght=len(nums)
    if numsLenght==1:
        return nums[0]
    if numsLenght==2:
        return max(nums[0],nums[1])
    if numsLenght==3:
        return max(nums[0],nums[1],nums[2])
    #创建状态转移矩阵
    dp=[0 for _ in range(numsLenght)]
    state=[False for _ in range(numsLenght)]
    dp[0]=nums[0]
    state[0]=True
    dp[1]=nums[1]
    dp[2]=nums[0]+nums[2]
    state[2]=True
    #循环
    for i in range(3,numsLenght):
        #先不取最后一个数
        dp[i]=max(dp[i-1],dp[i-2]+nums[i])
        # print(dp[i])
    return dp[numsLenght-1]
def maxVal1(nums):
    k1=rob1(nums[:len(nums)-1])
    k2=rob1(nums[1:len(nums)])
    print(k1)
    print(k2)
    return max(k1,k2)
print(maxVal1(nums))
